#ifndef MEMALLOCATOR_HPP_
#define MEMALLOCATOR_HPP_

//#define WINDOWS
#define LINUX

//#define DEBUG
#define ADAPTER
#define PARENT(addr, size_num) ((addr) & ~(1<<(size_num)))     //drop the corresponding bit

#define BUDDY(addr, size_num)  ((addr) ^ (1<<(size_num)))      //invert the corresponding bit

#include <iostream>
#include <cstring>
#include <cstdio>

#ifdef WINDOWS
#define noexcept 
#endif

#ifdef LINUX
#include <fcntl.h>
#include <sys/mman.h>
#include <unistd.h>
#endif

#include <exception>
#include <string>


#ifndef ADAPTER
    #include <mutex>
    #define INIT_LOCK MemAlloc::init_lock.lock()
    #define DEINIT_LOCK MemAlloc::deinit_lock.lock()
    #define INIT_UNLOCK MemAlloc::init_lock.unlock()
    #define DEINIT_UNLOCK MemAlloc::deinit_lock.unlock()
#else
    #define INIT_LOCK MemAlloc::init_lock = true
    #define DEINIT_LOCK MemAlloc::deinit_lock = true
    #define INIT_UNLOCK MemAlloc::init_lock = false
    #define DEINIT_UNLOCK MemAlloc::deinit_lock = false
#endif


template <typename T>
class Garbage;

class MemAllocImpl;
class SmartPtrImpl;

template <class T> class SmartPtr;
class ReleasedList;

template <typename T>
class List;

template <typename T>
class GarbageCollector;

template <typename T>
class Garbage;


//! Memory Allocator interface class
/*! To use MemAlloc class for memory management you should first call Init method.
Finaly you should call Deinit method. To allocate some memory you should use
Alloc call and next play a lot with SmartPtr's. When you suppose that you don't
need memory, please call Free method. Please, look for SmartPtr documentation
for more information. */
class MemAlloc {
public:
	template <class T>
	friend class SmartPtr;

	/*! Init function. This function must be called before the first call
	to Alloc; Please, don't forget to call Deinit after Init
	*/
	/*!
	\param mem_size RAM limit for allocator
	\param swap size for allocaor
	\param swap_path file path and name

	\throw std::bad_alloc exception on out-of-memory
	\throw std::ios_base::failure for file error
	\throw MemAllocException
	*/
	static void Init(size_t mem_size, uint64_t swap_size,
		const std::string& swap_path);

	//! Instance function returns correct MemAlloc&
	/*!
	\throw MemAllocException
	*/
	static MemAlloc& Instance();

	//! Deinitialize MemAlloc.
	/*
	\throw MemAllocException
	*/
	static void Deinit();

	//! Memory Allocate function.
	/*!
	Call to this function allocates array of elem_count elements of
	type T and returns SmartPtr<T> to acess allocated memory.
	Default array size is 1.
	*/
	/*
	\tparam T some concreate integer

	\param elem_count elements count in array we want to allocate.
	\return SmartPtr<T> which should be used to access memory

	\throw std::bad_alloc exception on out-of-memory
	\throw std::ios_base::failure for file error
	\throw MemAllocException
	*/
	template <class T>
	static SmartPtr<T>* Alloc(size_t elem_count = 1);

	//! Memory Free function.
	/*!
	Please be carefull with this function to prevent double-free.
	*/
	/*
	\tparam T some concreate integer

	\param ptr SmartPtr pointed to memory we want to free

	\throw std::bad_alloc exception on out-of-memory
	\throw std::ios_base::failure for file error
	\throw MemAllocException
	*/
	template <class T>
	static void Free(const SmartPtr<T>& ptr); //doesn't delete the pointer itself

	

private:
	static MemAlloc * inst;    //it is needed to make Instance() faster

	/*! Private constuctor getting private forward-declared class pointer with
	allocator implementation. It'll be called by Init method.
	*/
	MemAlloc(MemAllocImpl *pimpl);

	//! Deleted default constructor to preserve singleton properties
	MemAlloc() = delete;
	//! Deleted copy constructor to preserve singleton properties
	MemAlloc(const MemAlloc&) = delete;
	//! Deleted assign operator to preserve singleton properties
	MemAlloc& operator=(const MemAlloc&) = delete;

	//! MemAlloc private destructor
	~MemAlloc();

	//! Pointer to MemAllocImpl - MemAlloc interface implementation
	MemAllocImpl *pimpl_;

//when used with adapter, synchronization is conducted from adapter
#ifdef ADAPTER
        static bool init_lock;
        static bool deinit_lock;
#else
        static std::mutex init_lock;
        static std::mutex deinit_lock;
#endif
	static bool ma_inited;
};


//! SMartPtr interface class
/*! Object of this class is returned by Allocate in MemAlloc. One should use
SmartPtr's instead of usual C pointers everywhere in his code. This will
allow MemAlloc to know when memory is actively used and when it may be
unloaded to a swap area.
*/
template <class T>
class SmartPtr {
    
        SmartPtr(){pimpl_ = 0;}      
public:
        friend class Garbage<SmartPtr>;        

	/*! Constructor getting implementation pointer is only way to
	construct SmartPtr

	\param pimpl pointer to a realization
	\throw std::bad_alloc exception on out-of-memory
	*/
	SmartPtr(SmartPtrImpl *pimpl);

	/*! Simple copy constructor for reference counter
	\throw std::bad_alloc exception on out-of-memory
	*/
	SmartPtr(const SmartPtr<T>& ptr);

	//! Simple destructor for reference counter
	~SmartPtr();

	/*! Simple operator = for reference counter
	\throw std::bad_alloc exception on out-of-memory
	*/
	SmartPtr& operator=(const SmartPtr& ptr);

	SmartPtr(SmartPtrImpl& pimpl);


	///@{
	/*! Usual smart-pointer access operators. Access may take a lot of time
	because of possible swapping. These functions may throw!

	\throw std::bad_alloc exception on out-of-memory
	\throw std::ios_base::failure for file error
	\throw MemAllocException
	*/
	T& operator*();
	const T& operator*() const;
	T* operator->();
	const T* operator->() const;

	T& operator[](size_t idx);
	const T& operator[](size_t idx) const;
	///@}

	/*! Using Get/Release methods one can get usual C pointer from SmartPtr and lock
	memory for swapping until Release method called

	\throw std::bad_alloc exception on out-of-memory
	\throw std::ios_base::failure for file error
	\throw MemAllocException
	*/
	///@{
	T* Get();
	void Release();
	///@}

	void Free() const;
        
	//new and delete work with garbage
        static void* operator new(size_t size);
        static void operator delete(void* it);
        

private:
	int SubRef();

	SmartPtrImpl *pimpl_;
        SmartPtr *next; //for garbage collector and other purposes
};


//! General exception class for MemAlloc
class MemAllocException : public std::exception {
public:

	/*! An ErrorCode enum contains several constants which may be used in
	MemAllocException and derived exception classes */
	enum ErrorCode {
		E_NOMEM = ENOMEM, /*!< Not enough memory to load memory region from swap */
		E_NOBUFS = ENOBUFS, /*!< Too fragmented RAM */
		E_2BIG = E2BIG, /*!< Requested memory region is too big for allocator */
		E_MLINK = EMLINK, /*!< Lack of free memory identifiers */
		E_ALREADY = EALREADY, /*!< Allocator has already been initialized */
		E_UNINITIALIZED = ECANCELED, /*!< Allocator is unitialized */
		E_INVALID_INIT_SIZES = EBADF, /*!< Swap area is smaller than mem area */
		E_ACTIVE_MEMORY_FREE = EBUSY, /*!< Someone tried to Free memory which
									  is currently in use */

		//added:
		E_ACCES = EACCES,  // нет прав доступа к файлу swap_path
		E_FAULT = EFAULT,  // адрес swap_path недоступен, или такой блок не выделен или уже освобождён
		E_NOSPC = ENOSPC,  // файл swap_path невозможно создать так как в файловой системе нет места
		E_NOTDIR = ENOTDIR,// часть пути в swap_path, которая должна была быть папкой, оказалась мамкой)
		E_BUSY = EBUSY,    // файл swap_path уже занят
		E_FBIG = EFBIG     // запрашиваемый размер файла подкачки слишком большой    

	};


	//! No default constructor
	MemAllocException() = delete;
	//! Only constructor taking error_code and error_message
	MemAllocException(ErrorCode error_code, const std::string& error_msg);
	//! Virtual destructor
	virtual ~MemAllocException() noexcept;

	//! Standart std::exception what redefinition()
	virtual const char *what() const noexcept;
	//! GetErrorCode method returns ErrorCode
	virtual ErrorCode GetErrorCode() const noexcept;

private:
	std::string msg;
	ErrorCode code;
};


/*! Exception class for MemAlloc which is supposed to be used for fixable errors.
For example sometimes it's enough simply to wait for the empty memory in RAM.
This exception class is a convenient way to catch those exceptions and try again.
*/
class MemAllocWaitException : public MemAllocException {
public:
	//! Only constructor taking error_code and error_message
	MemAllocWaitException(size_t error_code, const std::string& error_msg);
	//! Virtual destructor
	virtual ~MemAllocWaitException() noexcept;
};


class MemAllocImpl {
public:
	friend class SmartPtrImpl;
	friend class ReleasedList;

	MemAllocImpl() = delete;

	MemAllocImpl(size_t mem_size, uint64_t swap_size, const std::string& swap_path);

	~MemAllocImpl();

	SmartPtrImpl* Alloc(size_t elem_count = 1);

	static void Free(SmartPtrImpl * smartptr, bool forced);

	uint64_t total_free;
	size_t mem_free;
	static MemAllocImpl *inst;
	
private:
	static int PAGESIZE;
	static const size_t min_chunk = 64; //each block holds no less than min_chunk bytes
	static const int min_chunk_log = 6; //log_2(min_chunk). Must be consistent with const above
	

	int N_swap;    //log_2(max_chunk/min_chunk)
	int N_mem;     //log_2(max_chunk/page_size)

	List<uint64_t> *free_swap_chunks; /*array of sets of free chunks of different sizes in swap*/
	List<size_t> *free_mem_pages;     /*array of sets of free chunks of different sizes in mem*/
	ReleasedList *released_mem_pages; /*released pages for each size in mem*/

	struct CountPageSwap{
		int get_count;
		int alloc_count;
		size_t mem_page;  //-1 if not in mem. in pages
		CountPageSwap() : get_count(0), alloc_count(0), mem_page(-1) {}
	} *count_page_swap;  /*array with numbers of gotten mem chunks
						 starting on that page of swap. It is used
						 for mapping/unmapping.*/

	char *mem;
#ifdef WINDOWS
	FILE* pFile;
#endif
#ifdef LINUX
	int dFile;
#endif

	size_t m_size;                //size of memory
	uint64_t s_size;              //size of swap

	size_t FindMem(int sz_num);   //gives a chunk in memory of the size number sz_num

	char *SwapToMem(SmartPtrImpl * ptr);  //put data of ptr in mem (it must be in swap)

};


class SmartPtrImpl {
public:
	friend class MemAllocImpl;
	friend class ReleasedList;
        friend class Garbage<SmartPtrImpl>;
        
	SmartPtrImpl();
	SmartPtrImpl(char* pValue);
	SmartPtrImpl(const SmartPtrImpl& sp);
	SmartPtrImpl(const SmartPtrImpl* sp);
	~SmartPtrImpl();
	SmartPtrImpl& operator =(const SmartPtrImpl& sp);

	void Release();
	char* Pointer(bool get);  //get indicated if get-counter should be incremented
	void RefDec();
	void RefInc();
        
        static void* operator new(size_t size);
        static void operator delete(void* it);

private:
	char* pData;
	uint64_t offset;   //in min_chunk units
	int sz_num;        //number of size of chunk, pointed by this
	int page_size_num;
	size_t size;        //don't need it with map

	size_t count;       //reference counter (for SmartPointer)
	size_t get_count;   //number of gets (for allocator)

	enum SPState {
		INVALID,
		IN_MEM,
		IN_SWAP,
		UNINITED,
		DELETED
	} state;
        
        SmartPtrImpl *next; //for garbage collector and other purposes
};


/*
\throw std::bad_alloc exception on out - of - memory
*/
template <class T>
SmartPtr<T>::SmartPtr(SmartPtrImpl& pimpl) {
	pimpl_ = &pimpl;
	pimpl_->RefInc();
}


/*
\throw std::bad_alloc exception on out - of - memory
*/
template <class T>
SmartPtr<T>::SmartPtr(SmartPtrImpl *pimpl) {
	pimpl_ = pimpl;
	pimpl_->RefInc();
}


/*! Simple copy constructor for reference counter
\throw std::bad_alloc exception on out-of-memory
*/
template <class T>
SmartPtr<T>::SmartPtr(const SmartPtr<T>& p) {
	pimpl_ = p.pimpl_;
	pimpl_->RefInc();
}


/*! Simple operator = for reference counter
\throw std::bad_alloc exception on out-of-memory
*/
template <class T>
SmartPtr<T>& SmartPtr<T>::operator=(const SmartPtr<T>& ptr) {
	if (pimpl_ == ptr.pimpl_){
		pimpl_->RefDec();
	}
	pimpl_ = ptr.pimpl_;
	return *this;
}


template <class T>
SmartPtr<T>::~SmartPtr() {
    if (pimpl_)
	pimpl_->RefDec();
}


template <class T>
void SmartPtr<T>::Free() const {
	if (!MemAlloc::ma_inited){
		throw MemAllocException(MemAllocException::E_UNINITIALIZED, std::string("Allocator is not inited"));
	}
	MemAllocImpl::Free(pimpl_, 0);
}


template <class T>
T* SmartPtr<T>::Get() {
	if (!MemAlloc::ma_inited){
		throw MemAllocException(MemAllocException::E_UNINITIALIZED, std::string("Allocator is not inited"));
	}
	char* res = pimpl_->Pointer(true);
	if (res == 0){
		throw ;//"unable to get" !!!
	}
	return res;
}


template <class T>
void SmartPtr<T>::Release() {
	if (!MemAlloc::ma_inited){
		throw MemAllocException(MemAllocException::E_UNINITIALIZED, std::string("Allocator is not inited"));
	}
	pimpl_->Release();
}


/*
\throw std::bad_alloc exception on out-of-memory
\throw std::ios_base::failure for file error
\throw MemAllocException
*/
template <class T>
T& SmartPtr<T>::operator*() {
	return *((T*)pimpl_->Pointer(false));
}


template <class T>
const T& SmartPtr<T>::operator*() const {
	return *((T*)pimpl_->Pointer(false));
}


template <class T>
T* SmartPtr<T>::operator->() {
	return (T*)pimpl_->Pointer(false);
}


template <class T>
const T* SmartPtr<T>::operator->() const {
	return (T*)pimpl_->Pointer(false);
}


template <class T>
T& SmartPtr<T>::operator[](size_t idx) {
	//array bounds? !!!
	return *(((T*)pimpl_->Pointer(false)) + idx);
}


template <class T>
const T& SmartPtr<T>::operator[](size_t idx) const {
	//check array bounds? !!!
	return *(pimpl_->Pointer(false) + idx);
}



template <typename T>
void* SmartPtr<T>::operator new(size_t size){
        return Garbage<SmartPtr<T>>::Pop();
}

template <typename T>
void SmartPtr<T>::operator delete(void* it){
       Garbage<SmartPtr<T>>::Push( (SmartPtr<T>*) it );
}



/*
\throw std::bad_alloc exception on out-of-memory
\throw std::ios_base::failure for file error
\throw MemAllocException
*/
template <class T>
void MemAlloc::Free(const SmartPtr<T>& ptr) {
    DEINIT_LOCK;
    if (ma_inited) {
        try{
            ptr.Free();
            DEINIT_UNLOCK;
        }
        catch (std::exception &e){
            DEINIT_UNLOCK;
            throw e;
        }
        catch(...){
            DEINIT_UNLOCK;
        }
    }
    else {
        DEINIT_UNLOCK;
        throw MemAllocException(MemAllocException::E_UNINITIALIZED, std::string("Allocator is not inited"));
    }
}


/*
\throw std::bad_alloc exception on out-of-memory
\throw std::ios_base::failure for file error
\throw MemAllocException
*/
template <class T>
SmartPtr<T>* MemAlloc::Alloc(size_t elem_count) {
    
    DEINIT_LOCK;   
    if (ma_inited) {
        try{
            size_t sz = elem_count*sizeof(T);
            SmartPtrImpl* spi;
            spi = inst->pimpl_->Alloc(sz);
            DEINIT_UNLOCK;
            return new SmartPtr<T>(spi);
        }
        catch (MemAllocException& e) {
            DEINIT_UNLOCK;
            throw e;
        }
        catch (std::bad_alloc& e){
            DEINIT_UNLOCK;
            throw e;
        }
        catch (std::ios_base::failure& e){
            DEINIT_UNLOCK;
            throw e;
        }
        catch(std::exception &e){
            DEINIT_UNLOCK;
            throw e;
        }
        catch(...){
            DEINIT_UNLOCK;
        }
    }
    else {
        DEINIT_UNLOCK;
        throw MemAllocException(MemAllocException::E_UNINITIALIZED, std::string("Allocator is not inited"));
    }
    
}


template <typename T>
class Node{
	friend class List<T>;
	friend class MemAllocImpl;
	friend class ReleasedList;
        friend class Garbage<Node<T>>;
	T value;
	Node* next;
public:
        static void* operator new(size_t size){
            return Garbage<Node<T>>::Pop();
        }
        
        static void operator delete(void* it){
            Garbage<Node<T>>::Push( (Node<T>*) it );
        }
        
        Node(T v):value(v){};
        Node(){};
};


template <typename T>
class GarbageCollector{
    friend class Garbage<T>;
    T* head;
    Garbage<T>* head_block;
    
    GarbageCollector(){
        head = 0;
        head_block = 0;
    }
    
    ~GarbageCollector(){
        this->Wipe();    /*each type that is using GarbageCollector has an object, cleaning
			is conducted in destructor (to avoid memory leaking)*/
        
    }
    void Wipe();
};

template <typename T>
class Garbage{
        friend class GarbageCollector<T>;
        friend class Node<uint64_t>;
        friend class SmartPtrImpl;
        friend class SmartPtr<T>;
        friend class SmartPtr<char>;
	T* item;
	Garbage* next;
	static T* Pop();
        static void Push(T* it);
        static GarbageCollector<T> collector_;
public:
        static void Wipe(){
            collector_.Wipe();
        };
};

template <typename T>
GarbageCollector<T> Garbage<T>::collector_ = GarbageCollector<T>();


template <typename T>
T* Garbage<T>::Pop(){
    const int SIZE = 32*1024;       //number of instances, allocated at a time (if necessary)
    if (Garbage<T>::collector_.head){
        T* ret = Garbage<T>::collector_.head;
        Garbage<T>::collector_.head = Garbage<T>::collector_.head->next;
        return ret;
    }
    
    Garbage *garb = new Garbage<T>();;
    if (!Garbage<T>::collector_.head_block){
        Garbage<T>::collector_.head_block = garb;        
    }
    else{
        garb->next = collector_.head_block->next;
        collector_.head_block->next = garb;
    }
    
    T* top = new T[SIZE];
    garb->item = top;    
    for (int i = 0; i < SIZE - 2; i++){
        top[i].next= top + i + 1;
    }
    top[SIZE - 2].next = collector_.head;
    collector_.head = top;
    return top + SIZE - 1;
}


template <typename T>
void Garbage<T>::Push(T* it){
    it->next = collector_.head;
    collector_.head = it;
}

template <typename T>
void GarbageCollector<T>::Wipe(){
    Garbage<T> *garb = head_block;
    while (head_block){
        garb = head_block->next;
        delete[] head_block->item;
        delete head_block;
        head_block = garb;
    }
    head = 0;
}


template <typename T>
class List{
	Node<T>* head;
	Node<T>* tail;
public:
	List();
	T Insert(T value, size_t block_size, bool merge);/* if merge == true, remove the buddy and return address of
							a bigger block, or just insert and return 0 if there is no buddy there */
	T Pop(); //erase one node from the list and give it's value (0 on fail)

	static void Merge(List<T>* lists, int sz_num, int top_sz_num, T chunk_num);
};


class ReleasedList{
	Node<uint64_t> *head;
	Node<uint64_t> *tail;
	int num;
public:
	size_t Pop(int num);
	void Push(uint64_t page);
	ReleasedList();
};


template <typename T>
List<T>::List(){
	head = new Node<T>(0);
	tail = new Node<T>(~0);
	head->next = tail;
}


//if 0 returned then there was common insertion
//	else it is a merged block place, and it isn't in any list after return
//block_size is in min_chunk units
template <typename T>
T List<T>::Insert(T value, size_t block_size, bool merge){
	T buddy = (value ^ block_size);
	Node<T> *pred = head;
	Node<T> *curr = head->next;
	while (1){
		//don't check tail as it has highest possible value

		if (curr->value == buddy && merge){
                        //removing buddy
			pred->next = curr->next;
			//utilize this node
			delete curr;
			//return merged block
			return (value & ~block_size);
		}
		else if (curr->value >= value){
			//inserting
			Node<T> *node = new Node<T>(value);
			node->next = curr;
			pred->next = node;
			return -1;
			}
                else {
                        pred = curr;
                        curr = curr->next;
                }
	}
	
}

template <typename T>
T List<T>::Pop(){
	Node<T> *curr = head->next;
	if (curr == tail){
		return (T)-1;
	}
	head->next = curr->next;
	T val = curr->value;
	delete curr;
	return val;
}


/* go up the list of lists starting with sz_num,
and insert the blocks. First insert chunk_num,
and then the blocks returned by insert function (merged ones).
On the top_sz_num do insert without merge.
This process stops when merge doesn't occur, or when top_sz_num is
reached. */

template <typename T>
void List<T>::Merge(List<T>* lists, int sz_num, int top_sz_num, T chunk_num){
	int j = sz_num;
	T tmp = lists[j].Insert(chunk_num, (1 << j), true);
	j++;
	//inserting merged chunks back
	while (j < top_sz_num && tmp != -1){
		tmp = lists[j].Insert(tmp, (1 << j), true);
		j++;
	}
	if (j == top_sz_num && tmp != -1){
		lists[j].Insert(tmp, (1 << j), false); //no merging for this one
	}
}



#endif //MEMALLOCATOR_HPP_
